package com.sicheng.lc.杂题.路径问题;

import java.util.ArrayDeque;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/17 14:50
 */
public class 访问所有节点的最短路径 {
    //https://leetcode.cn/problems/shortest-path-visiting-all-nodes/
    public int shortestPathLength(int[][] g) {
        int n = g.length;
        boolean[][] visit = new boolean[n][1 << n];
        ArrayDeque<int[]> deque = new ArrayDeque<>(n << 2);
        for (int i = 0; i < n; i++) {
            deque.offer(new int[]{i, 1 << i});
            visit[i][1 << i] = true;
        }
        int step = 0;

        while (!deque.isEmpty()) {
            int size = deque.size();
            step++;
            for (int m = 0; m < size; m++) {
                int[] p = deque.poll();
                assert p != null;
                for (int x : g[p[0]]) {
                    int mask = p[1] | (1 << x);
                    if (!visit[x][mask]) {
                        if (mask == (1 << n) - 1) {
                            return step;
                        }
                        deque.offer(new int[]{x, mask});
                        visit[x][mask] = true;
                    }
                }
            }
        }

        return 0;
    }
}
